package com.honeywen.mymvc.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 4. 寻找两个有序数组的中位数
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
 *
 * @author wangwei
 * @date 2018/12/7 下午2:55
 */
public class MedianTest {

    private static int[] ints = new int[100];

    private static void fillArray() {
        for (int i = 0; i < 100; i++) {
            ints[i] = i + 1;
        }
    }

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
        System.out.println(findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));

        System.out.println(findMedianSortedArrays2(new int[]{1, 3}, new int[]{2}));
        System.out.println(findMedianSortedArrays2(new int[]{1, 2}, new int[]{3, 4}));
        System.out.println(findMedianSortedArrays3(new int[]{1, 3}, new int[]{2}));
        System.out.println(findMedianSortedArrays3(new int[]{1, 2}, new int[]{3, 4}));


    }


    public static int binarySearch(int[] nums, int key) {
        int low = 0, high = nums.length - 1, mid = 0;

        while (low <= high) {
            System.out.println("search");
            mid = low + (high - low) / 2;
            if (nums[mid] == key) {
                return mid;
            }
            if (nums[mid] > key) {
                high = mid - 1;

            } else {
                low = mid + 1;
            }

        }

        return low;

    }


    public static double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0 && n == 0) {
            return 0;
        }

        if (m == 0) {
            return n % 2 == 1 ? nums2[n / 2] : (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
        }

        if (n == 0) {
            return m % 2 == 1 ? nums1[m / 2] : (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
        }

        if (m > n) {
            return findMedianSortedArrayHelper(nums1, nums2);
        }

        return findMedianSortedArrayHelper(nums2, nums1);

    }

    private static double findMedianSortedArrayHelper(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int low1 = 0;
        int high1 = m - 1;
        int low2 = 0;
        int high2 = n - 1;

        int mid = low1 + (high1 - low1) / 2;
        int pos = binarySearch(nums2, nums1[mid]);
        int num = mid + pos;
        // 如果 nums1[mid] 在 num2 中，
        if (num == (m + n) / 2) {
            if ((m + n) % 2 == 1) {
                return nums1[mid];
            }

            int next = 0;
            if ((mid > 0 && pos > 0)) {
                next = nums1[mid - 1] > nums2[pos - 1] ? nums1[mid - 1] : nums2[pos - 1];
            } else if (pos > 0) {
                next = nums2[pos - 1];
            } else if (mid > 0) {
                next = nums1[mid - 1];
            }
            return (nums1[mid] + next) / 2.0;

        }

        if (num < (m + n) / 2) {
            low1 = mid + 1;
            low2 = pos;
            if (high1 - low1 > high2 - low2) {
                return findMedianSortedArrayHelper(nums1, nums2);
            }
            return findMedianSortedArrayHelper(nums2, nums1);
        }

        if (num > (m + n) / 2) {
            high1 = mid - 1;
            high2 = pos - 1;
            if (high1 - low1 > high2 - low2) {
                return findMedianSortedArrayHelper(nums1, nums2);
            }
            return findMedianSortedArrayHelper(nums2, nums1);
        }


        return 0;
    }

    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {

        if (nums1.length > nums2.length) {
            return findMedianSortedArrays2(nums2, nums1);
        }
        int T = nums1.length + nums2.length;
        int low = -1;
        int high = -1;
        int median = (T - 1) / 2;
        boolean isOdd = false;
        if ((T % 2) != 0) {
            isOdd = true;
        }

        int s = 0, e = nums1.length - 1;
        while (s <= e) {
            int m = s + (e - s) / 2;
            if ((median - m - 1) < 0 || nums1[m] >= nums2[median - m - 1]) {
                e = m - 1;
                low = m;
                high = median - m;
            } else {
                s = m + 1;
            }
        }

        if (low == -1) {
            if (isOdd) {
                return nums2[median - nums1.length];

            } else {
                return (nums2[median - nums1.length] + nums2[median - nums1.length + 1]) / 2.0;
            }
        } else {
            if (isOdd) {
                return nums1[low] < nums2[high] ? nums1[low] : nums2[high];
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(nums1[low]);
                if (low + 1 < nums1.length) {
                    list.add(nums1[low + 1]);
                }
                list.add(nums2[high]);
                if (high + 1 < nums2.length) {
                    list.add(nums2[high + 1]);
                }
                Collections.sort(list);
                return (double) (list.get(0) + list.get(1)) / 2.0;

            }
        }

    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int m = nums1.length;
        int n = nums2.length;


        int len = (m + n) / 2;

        int[] ints = new int[len + 1];
        int ia = m - 1;
        int ib = n - 1;

        for (int i = len; i >= 0; i--) {

            if (ia >= 0 && ib < 0) {
                ints[i] = nums1[ia--];
                continue;

            }

            if (ia < 0 && ib >= 0) {
                ints[i] = nums2[ib--];
                continue;
            }

            if (ia >= 0 && ib >= 0) {
                if (nums1[ia] > nums2[ib]) {
                    ints[i] = nums1[ia--];

                } else {
                    ints[i] = nums2[ib--];
                }
            }

        }

        double res = 0;
        if ((m + n) % 2 == 0) {
            res = (ints[0] + ints[1]) / 2.0;
        } else {
            res = ints[0];
        }
        return res;

    }
}
